{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Median of Two Sorted Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #divide-and-conquer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #分治"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMedianSortedArrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找两个正序数组的中位数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个大小分别为 <code>m</code> 和 <code>n</code> 的正序（从小到大）数组&nbsp;<code>nums1</code> 和&nbsp;<code>nums2</code>。请你找出并返回这两个正序数组的 <strong>中位数</strong> 。</p>\n",
    "\n",
    "<p>算法的时间复杂度应该为 <code>O(log (m+n))</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [1,3], nums2 = [2]\n",
    "<strong>输出：</strong>2.00000\n",
    "<strong>解释：</strong>合并数组 = [1,2,3] ，中位数 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [1,2], nums2 = [3,4]\n",
    "<strong>输出：</strong>2.50000\n",
    "<strong>解释：</strong>合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums1.length == m</code></li>\n",
    "\t<li><code>nums2.length == n</code></li>\n",
    "\t<li><code>0 &lt;= m &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= m + n &lt;= 2000</code></li>\n",
    "\t<li><code>-10<sup>6</sup> &lt;= nums1[i], nums2[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [median-of-two-sorted-arrays](https://leetcode.cn/problems/median-of-two-sorted-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [median-of-two-sorted-arrays](https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3]\\n[2]', '[1,2]\\n[3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        half = (len(nums1) + len(nums2)) // 2\n",
    "        if len(nums2) < len(nums1):\n",
    "            nums1, nums2 = nums2, nums1\n",
    "        l, r = 0, len(nums1) - 1\n",
    "        while True: # list里只有一个元素 or 头尾越界还要继续循环\n",
    "            i = (l + r) // 2\n",
    "            j = half - i - 2 # 0-based index\n",
    "            Aleft = nums1[i] if i >= 0 else float(\"-infinity\")\n",
    "            Aright = nums1[i + 1] if (i + 1) < len(nums1) else float(\"infinity\")\n",
    "            Bleft = nums2[j] if j >= 0 else float(\"-infinity\")\n",
    "            Bright = nums2[j + 1] if (j + 1) < len(nums2) else float(\"infinity\")\n",
    "\n",
    "            # partition is correct\n",
    "            if Aleft <= Bright and Bleft <= Aright:\n",
    "                # odd\n",
    "                if (len(nums1) + len(nums2)) % 2:\n",
    "                    return min(Aright, Bright)\n",
    "                # even\n",
    "                return (max(Aleft, Bleft) + min(Aright, Bright)) / 2\n",
    "            elif Aleft > Bright:\n",
    "                r = i - 1\n",
    "            else:\n",
    "                l = i + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        import math\n",
    "\n",
    "        def get_median(nums):\n",
    "            mid = math.floor(len(nums) / 2)\n",
    "            if len(nums) % 2 == 0:\n",
    "                return (nums[mid] + nums[mid - 1]) / 2\n",
    "            else:\n",
    "                return nums[mid]\n",
    "\n",
    "        if len(nums1) == 0 or len(nums2) == 0:\n",
    "            if len(nums1) == 0:\n",
    "                return get_median(nums2)\n",
    "            if len(nums2) == 0:\n",
    "                return get_median(nums1)\n",
    "\n",
    "        l1, l2 = len(nums1), len(nums2)\n",
    "        # l = l1 + l2\n",
    "        # mid = l / 2\n",
    "\n",
    "        i, j = 0, 0\n",
    "        n_nums = []\n",
    "        while (i < l1 and j < l2):\n",
    "            if nums2[j] > nums1[i]:\n",
    "                n_nums.append(nums1[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                n_nums.append(nums2[j])\n",
    "                j += 1\n",
    "        if i < l1:\n",
    "            n_nums += nums1[i:]\n",
    "        if j < l2:\n",
    "            n_nums += nums2[j:]\n",
    "        print(n_nums)\n",
    "        return get_median(n_nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        def kth(A, B, k):\n",
    "            if len(A) > len(B):\n",
    "                A, B = B, A\n",
    "            if not A:\n",
    "                return B[k]\n",
    "            if k == len(A) + len(B) - 1:\n",
    "                return max(A[-1], B[-1])\n",
    "\n",
    "            i = min(len(A)-1, k // 2)\n",
    "            j = k - i\n",
    "\n",
    "            if A[i] > B[j]:\n",
    "                return kth(A[:i], B[j:], i)\n",
    "            else:\n",
    "                return kth(A[i:], B[:j], j)\n",
    "            \n",
    "        l = len(nums1) + len(nums2)\n",
    "        r1 = kth(nums1, nums2, l // 2)\n",
    "        if l % 2 != 0:\n",
    "            return r1 * 1.0\n",
    "        r2 = kth(nums1, nums2, l // 2 - 1)\n",
    "        return (r1 + r2) / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        def findKth(A, B, k):\n",
    "            if len(A) == 0:\n",
    "                return B[k-1]\n",
    "            if len(B) == 0:\n",
    "                return A[k-1]\n",
    "            if k == 1:\n",
    "                return min(A[0], B[0])\n",
    "            \n",
    "            if len(B) < k // 2  :\n",
    "                return findKth(A[k // 2:], B, k - k // 2)\n",
    "            # a = A[k // 2 - 1]\n",
    "            # b = B[k // 2 - 1]\n",
    "            elif (len(A) >= k//2 and A[k // 2 - 1] <= B[k // 2 - 1]):\n",
    "                return findKth(A[k // 2:], B, k - k // 2)\n",
    "            \n",
    "            elif len(A) < k // 2:\n",
    "                return findKth(A, B[k // 2:], k - k // 2)\n",
    "            # a = A[k // 2 - 1]\n",
    "            # b = B[k // 2 - 1]\n",
    "            elif (len(B) >= k//2 and A[k // 2 - 1] >= B[k // 2 - 1]):\n",
    "                return findKth(A, B[k // 2:], k - k // 2)\n",
    "            \n",
    "        n = len(nums1) + len(nums2)\n",
    "        if n % 2 == 1:\n",
    "            return findKth(nums1, nums2, n // 2 + 1)\n",
    "        else:\n",
    "            smaller = findKth(nums1, nums2, n // 2)\n",
    "            bigger = findKth(nums1, nums2, n // 2 + 1)\n",
    "            return (smaller + bigger) / 2.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        l = []\n",
    "        i = j1 = j2 = 0\n",
    "        len1 = len(nums1)\n",
    "        len2 = len(nums2)\n",
    "        while j1 < len1 and j2 <len2:\n",
    "            if nums1[j1] < nums2[j2]:\n",
    "                l.append(nums1[j1])\n",
    "                j1 += 1\n",
    "            else:\n",
    "                l.append(nums2[j2])\n",
    "                j2 += 1\n",
    "\n",
    "            #连接剩余部分\n",
    "        while j1<len1:\n",
    "            l.append(nums1[j1])\n",
    "            j1 += 1\n",
    "        while j2 < len2:\n",
    "            l.append(nums2[j2])\n",
    "            j2 += 1\n",
    "        return (l[(len1+len2+1)//2 - 1] + l[(len1+len2+2)//2 - 1])/2\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        m,n = len(nums1),len(nums2)\n",
    "        if n < m:\n",
    "            nums1,nums2,m,n = nums2,nums1,n,m\n",
    "        if n == 0:\n",
    "            raise ValueError\n",
    "        imin, imax, half = 0, m, (m + n + 1)//2\n",
    "        while imin <= imax:\n",
    "            i = (imin+imax)//2\n",
    "            j = half - i\n",
    "            #i太小，需要增大\n",
    "            if i<m and nums2[j-1] > nums1[i]:\n",
    "                imin = i+1\n",
    "            #i太大，需要减小\n",
    "            elif i>0 and  nums1[i-1] > nums2[j]:\n",
    "                imax = i-1\n",
    "            else:\n",
    "                if i==0:\n",
    "                    max_of_left = nums2[j-1]\n",
    "                elif j==0:\n",
    "                    max_of_left = nums1[i-1]\n",
    "                else:\n",
    "                    max_of_left = max(nums1[i-1], nums2[j-1])\n",
    "                if (m+n)%2 == 1:\n",
    "                    return max_of_left\n",
    "                \n",
    "                if i==m:\n",
    "                    min_of_right = nums2[j]\n",
    "                elif j==n:\n",
    "                    min_of_right = nums1[i]\n",
    "                else:\n",
    "                    min_of_right = min(nums1[i], nums2[j])\n",
    "                return (max_of_left + min_of_right) / 2.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, A, B):\n",
    "        m, n = len(A), len(B)\n",
    "        if n < m:\n",
    "            m, n, A, B = n, m, B, A\n",
    "        # 计算leftMax, rightMin\n",
    "        # 二分法搜索i\n",
    "        imin, imax, halfLen = 0, m, (m+n+1)/2 # j=int(halfLen-i)\n",
    "        while imin <= imax: #二分查找的判断语句\n",
    "                i = int((imin+imax)/2)\n",
    "                j = int(halfLen-i)\n",
    "                if  i < m and j > 0 and A[i] < B[j-1]:\n",
    "                    imin = i + 1\n",
    "                elif  i > 0 and j < n and A[i-1] > B[j]:\n",
    "                    imax = i - 1\n",
    "                else:\n",
    "                    # i is perfect\n",
    "                    if i == 0:\n",
    "                        maxLeft = B[j-1]\n",
    "                    elif j == 0:\n",
    "                        maxLeft = A[i-1]\n",
    "                    else:\n",
    "                        maxLeft = max(A[i-1], B[j-1])\n",
    "                        \n",
    "                    if (m + n) % 2 == 1:\n",
    "                        return maxLeft\n",
    "                    else:\n",
    "                        if i == m:\n",
    "                             minRight = B[j]\n",
    "                        elif j == n: \n",
    "                            minRight = A[i]\n",
    "                        else:\n",
    "                            minRight = min(A[i], B[j])\n",
    "                    print(i,j, minRight, maxLeft)\n",
    "                    return (minRight+maxLeft)/2\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        if m > n:\n",
    "            m, n = n, m\n",
    "            nums1, nums2 = nums2, nums1\n",
    "        # 使 m<=n\n",
    "        \n",
    "        if m == 0:\n",
    "            # nums2 中位数\n",
    "            if n%2:  # 奇数\n",
    "                return nums2[n//2]\n",
    "            else:\n",
    "                return (nums2[n//2-1]+nums2[n//2])/2     \n",
    "        \n",
    "        # i, j 代表nums1, nums2中左边数组的个数\n",
    "        # low_1, high_1 代表i 的下限和上限\n",
    "        low_1 , high_1 = 0, m\n",
    "        \n",
    "        while low_1 <= high_1:\n",
    "            if (m+n)%2:  #奇数\n",
    "                i = (low_1 + high_1)//2\n",
    "                j = (m + n)//2 - i + 1\n",
    "            else:  #偶数\n",
    "                i = (low_1 + high_1)//2\n",
    "                j = (m + n)//2 - i\n",
    "        \n",
    "            # i 即 nums1 的中位, 保持左边与右边个数相等(或左比右多一) i + j = (m+n)//2 (+1) \n",
    "            print(i,j)\n",
    "            if i == 0 and nums2[j-1] <= nums1[i]:\n",
    "                if (m+n)%2:  # 奇数\n",
    "                    return nums2[j-1]\n",
    "                else:\n",
    "                    if j == n:\n",
    "                        return (nums2[j-1] + nums1[i])/2\n",
    "                    else:\n",
    "                        return (nums2[j-1] + min(nums1[i], nums2[j]))/2\n",
    "                \n",
    "            elif i == 0 and nums2[j-1] > nums1[i]:\n",
    "                low_1 = i + 1\n",
    "            \n",
    "            elif i == m and nums1[i-1] <= nums2[j]:\n",
    "                if (m+n)%2:  # 奇数\n",
    "                    return max(nums1[i-1], nums2[j-1])    \n",
    "                else:\n",
    "                    if j == 0:\n",
    "                        return (nums2[j] + nums1[i-1])/2\n",
    "                    else:\n",
    "                        return (max(nums1[i-1], nums2[j-1]) + nums2[j])/2\n",
    "                return max(nums1[i-1], nums2[j-1])\n",
    "            \n",
    "            elif i == m and nums1[i-1] > nums2[j]:\n",
    "                high_1 = i - 1\n",
    "            \n",
    "            \n",
    "            elif nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i]:\n",
    "                if (m+n)%2:  # 奇数\n",
    "                    return max(nums1[i-1], nums2[j-1])\n",
    "                else:  # 偶数\n",
    "                    return (max(nums1[i-1], nums2[j-1]) + min(nums1[i], nums2[j])) / 2\n",
    "            elif nums2[j-1] > nums1[i]:\n",
    "                low_1 = i + 1  \n",
    "                # 这里要+1 因为不存在 目标值在(i, i+1)之间这种情况, \n",
    "                # 一定存在一个i值能将其分成两个数量相等(或差1)的部分.  \n",
    "            elif nums1[i-1] > nums2[j]:\n",
    "                high_1 = i - 1\n",
    "                \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        newarray = sorted(nums1+nums2)\n",
    "        if len(newarray)%2 == 1:\n",
    "        \treturn newarray[len(newarray)//2]\n",
    "        else:\n",
    "        \treturn (newarray[len(newarray)//2] + newarray[len(newarray)//2 - 1])/2\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        if m > n:\n",
    "\t        nums1, nums2, m, n = nums2, nums1, n, m\n",
    "        if n == 0:\n",
    "\t        raise ValueError\n",
    "\n",
    "\t    # 这里本来 i+j = m-i + n-j 的，然后 j = (m+n)/2.这里用(m + n +1) // 2的原因是为了和下面的 “情况” 进行配合\n",
    "        imin, imax, half_len = 0, m, (m + n +1) // 2\n",
    "        while imin <= imax:\n",
    "\t        i = (imin + imax) // 2\n",
    "\t        j = half_len - i\n",
    "\t        if i < m and nums2[j-1] > nums1[i]:\n",
    "\t            # i is too small, must increase it\n",
    "\t            imin = i + 1\n",
    "\t        elif i > 0 and nums1[i-1] > nums2[j]:\n",
    "\t            # i is too big, must decrease it\n",
    "\t            imax = i - 1\n",
    "\t        else:\n",
    "\n",
    "\t            if i == 0: max_of_left = nums2[j-1]\n",
    "\t            elif j == 0: max_of_left = nums1[i-1]\n",
    "\t            else: max_of_left = max(nums1[i-1], nums2[j-1])\n",
    "\n",
    "\t            if (m + n) % 2 == 1:\n",
    "\t                return max_of_left\n",
    "\n",
    "\t            # 边界条件2\n",
    "\t            if i == m: \n",
    "\t            \tmin_of_right = nums2[j]\n",
    "\t            elif j == n:\n",
    "\t            \tmin_of_right = nums1[i]\n",
    "\t            else: min_of_right = min(nums1[i], nums2[j])\n",
    "\t            return (max_of_left + min_of_right) / 2.0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        if m < n:\n",
    "            m ,n = n, m\n",
    "            nums1, nums2 = nums2, nums1\n",
    "            \n",
    "        if (m + n) % 2 == 0:\n",
    "            return self.twoMedianSort(m, n, nums1, nums2)\n",
    "        else:\n",
    "            return self.oneMedianSort(m ,n, nums1, nums2)\n",
    "    \n",
    "    def twoMedianSort(self, m, n, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type m, n: int\n",
    "        :type nums1, nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        assert m >= n\n",
    "        l = (m + n) // 2\n",
    "        if (n == 0):\n",
    "            return (nums1[m // 2] + nums1[(m-1) // 2]) / 2\n",
    "        \"\"\"\n",
    "        Case 1: median is greater than all elements in nums2\n",
    "        Case 2: median is smaller than all elements in nums2\n",
    "        Case 3: m = n, the lower median is smaller than all elements in nums1(nums2), the upper median is greater than all elements in nums2(nums1)\n",
    "        Case 4: nums2 contains only one element and is one side of element\n",
    "        Case 5: otherwise\n",
    "        \"\"\"\n",
    "        #Case 3\n",
    "        if (m == n):\n",
    "            if (nums1[-1] <= nums2[0]):\n",
    "                return (nums1[-1] + nums2[0]) / 2\n",
    "            elif (nums1[0] >= nums2[-1]):\n",
    "                return (nums1[0] + nums2[-1]) / 2\n",
    "            else:\n",
    "                return self.binarySearchTwo(0, m-1, l, m, n, nums1, nums2)\n",
    "        #Case 1\n",
    "        u = l - n # the rest elements in nums1\n",
    "        assert u > 0 # nums1[u], nums1[u-1] are the two median \n",
    "        if (nums1[u-1] >= nums2[-1]):\n",
    "            return (nums1[u-1] + nums1[u]) / 2\n",
    "        \n",
    "        #Case 2\n",
    "        u = l-1\n",
    "        assert u > 0\n",
    "        if (nums1[u+1] <= nums2[0]):\n",
    "            return (nums1[u] + nums1[u+1]) / 2\n",
    "        \n",
    "        if (n == 1):\n",
    "            u = m // 2\n",
    "            if (nums1[u] <= nums2[0]) and (nums2[0] <= nums1[u+1]):\n",
    "                return (nums1[u] + nums2[0]) / 2\n",
    "            elif (nums1[u-1] <= nums2[0]) and (nums2[0] <= nums1[u]):\n",
    "                return (nums1[u] + nums2[0]) / 2\n",
    "        #Case 5\n",
    "        # In this case, we have to apply binarysearch\n",
    "        ret = self.binarySearchTwo(0, m-1, l, m, n, nums1, nums2)\n",
    "        return ret\n",
    "        \n",
    "    def oneMedianSort(self, m, n, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type m, n: int\n",
    "        :rtype nums1, nums2: List[int]\n",
    "        \"\"\"\n",
    "        assert m >= n\n",
    "        l = (m + n) // 2\n",
    "        if (n == 0):\n",
    "            return nums1[m // 2]\n",
    "        \"\"\"\n",
    "        Case 1: median is greater than all elements in nums2\n",
    "        Case 2: median is smaller than all elements in nums2\n",
    "        Case 3: otherwise\n",
    "        \"\"\"\n",
    "        \n",
    "        #Case 1\n",
    "        u = l - n\n",
    "        assert u >= 0\n",
    "        if (nums1[u] >= nums2[-1]):\n",
    "            return nums1[u]\n",
    "        \n",
    "        #Case 2\n",
    "        u = l\n",
    "        assert u > 0\n",
    "        if (nums1[u] <= nums2[0]):\n",
    "            return nums1[u]\n",
    "        \n",
    "        #Case 3\n",
    "        # two bound: [l+1-1,1] [l-n+1,n]\n",
    "        ret = self.binarySearchOne(0, m-1, l, m, n, nums1, nums2)\n",
    "        return ret\n",
    "        \n",
    "    def binarySearchOne(self, head, tail, l, m, n, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type head, tail, l, m, n: int\n",
    "        :type nums1, nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        assert head <= tail\n",
    "        # do binarysearch in [head, tail]\n",
    "        mid1 = (head + tail) // 2 # index for the first pivot\n",
    "        mid2 = l - mid1 - 1 # index for the second pivot\n",
    "        if (mid2 < 0):\n",
    "            if (mid2 == -1):\n",
    "                cdt1 = nums1[mid1]\n",
    "                cdt2 = min(nums1[mid1+1], nums2[0])\n",
    "                if (cdt1 <= cdt2):\n",
    "                    return (cdt1 + cdt2) / 2\n",
    "            return self.binarySearchOne(head, mid1-1, l, m, n, nums1, nums2)\n",
    "        elif (mid2 >= n):\n",
    "            return self.binarySearchOne(mid1+1, tail, l, m, n, nums1, nums2)\n",
    "        cdt1 = max(nums1[mid1], nums2[mid2])\n",
    "        assert mid1 + 1 < m or mid2 + 1 < n\n",
    "        if (mid1 + 1 == m):\n",
    "            cdt2 = nums2[mid2 + 1]\n",
    "        elif (mid2 + 1 == n):\n",
    "            cdt2 = nums1[mid1 + 1]\n",
    "        else:\n",
    "            cdt2 = min(nums2[mid2+1], nums1[mid1+1])\n",
    "            \n",
    "        if (cdt1 <= cdt2):\n",
    "            return cdt1\n",
    "        else:\n",
    "            if (mid1 + 1 == m):\n",
    "                \"\"\"\n",
    "                [....,a]\n",
    "                [...,b, c,...]\n",
    "                \"\"\"\n",
    "                assert nums1[mid1] > nums2[mid2 + 1]\n",
    "                return self.binarySearchOne(head, mid1-1, l, m, n, nums1, nums2) # left query\n",
    "            elif (mid2 + 1 == n):\n",
    "                \"\"\"\n",
    "                [...,a,b,......]\n",
    "                [....c]\n",
    "                \"\"\"\n",
    "                assert nums2[mid2] > nums1[mid1 + 1]\n",
    "                return self.binarySearchOne(mid1+1, tail, l, m, n, nums1, nums2) # right query\n",
    "            else:\n",
    "                \"\"\"\n",
    "                [....,a,b,....]\n",
    "                [....,c,d,....]\n",
    "                \"\"\"\n",
    "                if (nums1[mid1] > nums2[mid2+1]):\n",
    "                    return self.binarySearchOne(head, mid1-1, l, m, n, nums1, nums2) # left query\n",
    "                elif (nums2[mid2] > nums1[mid1+1]):\n",
    "                    return self.binarySearchOne(mid1+1, tail, l, m, n, nums1, nums2) # right query\n",
    "        assert False\n",
    "        \n",
    "    def binarySearchTwo(self, head, tail, l, m, n, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type head, tail, l, m, n: int\n",
    "        :type nums1, nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        print(head, tail)\n",
    "        assert head <= tail\n",
    "        \n",
    "        mid1 = (head + tail) // 2\n",
    "        mid2 = l - mid1 - 2\n",
    "        print(mid1, \"and\", mid2)\n",
    "        if (mid2 < 0):\n",
    "            if mid2 == -1:\n",
    "                cdt1 = nums1[mid1]\n",
    "                cdt2 = min(nums2[0], nums1[mid1+1])\n",
    "                if (cdt1 <= cdt2):\n",
    "                    return (cdt1+cdt2) / 2\n",
    "            return self.binarySearchTwo(head, mid1-1, l, m, n, nums1, nums2)\n",
    "        elif (mid2 >= n):\n",
    "            return self.binarySearchTwo(mid1+1, tail, l, m, n, nums1, nums2)\n",
    "        # (mid1 + 1) + (mid2 + 1) = l\n",
    "        cdt1 = max(nums1[mid1], nums2[mid2])\n",
    "        assert mid1 + 1 < m or mid2 + 1 < n\n",
    "        \n",
    "        if (mid1 + 1 == m):\n",
    "            cdt2 = nums2[mid2+1]\n",
    "        elif (mid2 + 1 == n):\n",
    "            cdt2 = nums1[mid1+1]\n",
    "        else:\n",
    "            cdt2 = min(nums2[mid2+1], nums1[mid1+1])\n",
    "        \n",
    "        if (cdt1 <= cdt2):\n",
    "            return (cdt1 + cdt2) / 2\n",
    "        else:\n",
    "            if (mid1 + 1 == m):\n",
    "                \"\"\"\n",
    "                [....,a]\n",
    "                [...,b, c,...]\n",
    "                \"\"\"\n",
    "                assert nums1[mid1] > nums2[mid2 + 1]\n",
    "                return self.binarySearchTwo(head, mid1-1, l, m, n, nums1, nums2) # left query\n",
    "            elif (mid2 + 1 == n):\n",
    "                \"\"\"\n",
    "                [...,a,b,......]\n",
    "                [....c]\n",
    "                \"\"\"\n",
    "                assert nums2[mid2] > nums1[mid1 + 1]\n",
    "                return self.binarySearchTwo(mid1+1, tail, l, m, n, nums1, nums2) # right query\n",
    "            else:\n",
    "                \"\"\"\n",
    "                [....,a,b,....]\n",
    "                [....,c,d,....]\n",
    "                \"\"\"\n",
    "                if (nums1[mid1] > nums2[mid2+1]):\n",
    "                    return self.binarySearchTwo(head, mid1-1, l, m, n, nums1, nums2) # left query\n",
    "                elif (nums2[mid2] > nums1[mid1+1]):\n",
    "                    return self.binarySearchTwo(mid1+1, tail, l, m, n, nums1, nums2) # right query\n",
    "        assert False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        m,n=len(nums1),len(nums2)\n",
    "        \n",
    "        if m>n:\n",
    "            m,n,nums1,nums2=n,m,nums2,nums1\n",
    "            \n",
    "        imin,imax,half,maxleft,maxright=0,m,int((m+n+1)/2),None,None\n",
    "        \n",
    "        while imin<=imax:\n",
    "            i=int((imin+imax)/2)\n",
    "            j=half-i\n",
    "            \n",
    "            if i>0 and nums1[i-1]>nums2[j]:\n",
    "                imax=i-1\n",
    "            elif i<m and nums2[j-1]>nums1[i]:\n",
    "                imin=i+1\n",
    "            else:\n",
    "                if i==0: \n",
    "                    maxleft=nums2[j-1]\n",
    "                elif j==0:\n",
    "                    maxleft=nums1[i-1]\n",
    "                else:\n",
    "                    maxleft=max(nums1[i-1],nums2[j-1])\n",
    "                    \n",
    "                if (m+n)%2!=0:\n",
    "                    return maxleft\n",
    "                \n",
    "                if i==m:\n",
    "                    maxright=nums2[j]\n",
    "                elif j==n:\n",
    "                    maxright=nums1[i]\n",
    "                else:\n",
    "                    maxright=min(nums1[i],nums2[j])\n",
    "                \n",
    "                return (maxleft+maxright)/2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        nums3=nums1+nums2\n",
    "        nums3.sort(reverse=False)\n",
    "        numl=len(nums3)\n",
    "        if nums3:\n",
    "            if numl%2==0:\n",
    "                return (nums3[numl//2]+nums3[numl//2-1])/2\n",
    "            else:\n",
    "                return nums3[numl//2]\n",
    "        else:\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, nums1, nums2, a, b, c, d, k):\n",
    "        print(a,b,c,d,k)\n",
    "        m1 = min(b, a+k//2)\n",
    "        m2 = min(d, c+k//2)\n",
    "        \n",
    "\n",
    "        \n",
    "        if b-a==0:\n",
    "            return nums2[k-1+c]\n",
    "        if d-c==0:\n",
    "            return nums1[k-1+a]\n",
    "        if k==1:\n",
    "            return min(nums1[a],nums2[c])\n",
    "        \n",
    "        if nums1[m1-1] >= nums2[m2-1]:\n",
    "            return self.f(nums1, nums2, a, b, m2, d, k-(m2-c))\n",
    "        elif nums1[m1-1] < nums2[m2-1]:\n",
    "            return self.f(nums1, nums2, m1, b, c, d, k-(m1-a))\n",
    "        \n",
    "        \n",
    "        \n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        k = (n1 + n2) // 2 \n",
    "        if (n1+n2) & 1 == 1: #奇数\n",
    "            return self.f(nums1, nums2, 0, n1, 0, n2, k +1)\n",
    "        else:\n",
    "            return (self.f(nums1, nums2, 0, n1, 0, n2, k) +\n",
    "                    self.f(nums1, nums2, 0, n1, 0, n2, k+1)) / 2\n",
    "    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: 'List[int]', nums2: 'List[int]') -> 'float':\n",
    "        li = nums1 + nums2\n",
    "        # insure it has run time complexity O(log(m+n)), we use quick sort.\n",
    "        Solution.quickSort(li, 0, len(li) - 1)\n",
    "        \n",
    "        if len(li)%2 == 0:\n",
    "            return (li[len(li)//2] + li[len(li)//2 - 1])/2\n",
    "        else:\n",
    "            return li[(len(li) - 1)//2]\n",
    "        \n",
    "    def partition(arr,low,high): \n",
    "        i = ( low-1 )         # index of smaller element \n",
    "        pivot = arr[high]     # pivot \n",
    "\n",
    "        for j in range(low , high): \n",
    "\n",
    "            # If current element is smaller than or \n",
    "            # equal to pivot \n",
    "            if   arr[j] <= pivot: \n",
    "\n",
    "                # increment index of smaller element \n",
    "                i = i+1 \n",
    "                arr[i],arr[j] = arr[j],arr[i] \n",
    "\n",
    "        arr[i+1],arr[high] = arr[high],arr[i+1] \n",
    "        return ( i+1 ) \n",
    "    \n",
    "    def quickSort(arr,low,high): \n",
    "        if low < high: \n",
    "\n",
    "            pi = Solution.partition(arr,low,high) \n",
    "\n",
    "            # Separately sort elements before \n",
    "            # partition and after partition \n",
    "            Solution.quickSort(arr, low, pi-1) \n",
    "            Solution.quickSort(arr, pi+1, high) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArray(self, nums):\n",
    "        length = len(nums)\n",
    "        mid = length // 2\n",
    "        is_even = (length % 2) is 0\n",
    "\n",
    "        if is_even:\n",
    "            print(nums)\n",
    "            print(mid)\n",
    "            print('is_even')\n",
    "            return (nums[mid - 1] + nums[mid]) / 2\n",
    "        else:\n",
    "            print(nums)\n",
    "            print(mid)\n",
    "            print('is_not_even')\n",
    "            return nums[mid] / 1\n",
    "            \n",
    "    \n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        if not nums1:\n",
    "            return self.findMedianSortedArray(nums2)\n",
    "        \n",
    "        if not nums2:\n",
    "            return self.findMedianSortedArray(nums1)\n",
    "        \n",
    "        length1 = len(nums1)\n",
    "        length2 = len(nums2)\n",
    "        \n",
    "        left1 = nums1[0]\n",
    "        left2 = nums2[0]\n",
    "        if left1 < left2:\n",
    "            del nums1[0]\n",
    "            if not nums1:\n",
    "                right2 = nums2.pop()\n",
    "                if not nums2:\n",
    "                    return (left1 + right2) / 2\n",
    "                return self.findMedianSortedArray(nums2)\n",
    "            else:\n",
    "                right1 = nums1[-1]\n",
    "                right2 = nums2[-1]\n",
    "                if right1 > right2:\n",
    "                    nums1.pop()\n",
    "                else:\n",
    "                    nums2.pop()\n",
    "                return self.findMedianSortedArrays(nums1, nums2)\n",
    "        else:\n",
    "            del nums2[0]\n",
    "            if not nums2:\n",
    "                right1 = nums1.pop()\n",
    "                if not nums1:\n",
    "                    return (left2 + right1) / 2\n",
    "                return self.findMedianSortedArray(nums1)\n",
    "            else:\n",
    "                right1 = nums1[-1]\n",
    "                right2 = nums2[-1]\n",
    "                if right1 > right2:\n",
    "                    nums1.pop()\n",
    "                else:\n",
    "                    nums2.pop()\n",
    "                return self.findMedianSortedArrays(nums1, nums2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        NewNum = sorted(nums1 + nums2)\n",
    "        length = len(NewNum)\n",
    "        if length%2 == 0:\n",
    "            aaa = int(length/2)\n",
    "            print(NewNum[aaa-1])\n",
    "            print(NewNum[aaa])\n",
    "            av = (NewNum[aaa-1] + NewNum[aaa])/2\n",
    "            return av\n",
    "        else:\n",
    "            index = int(length/2)\n",
    "            return (NewNum[index]+NewNum[index])/2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArray(self, nums):\n",
    "        length = len(nums)\n",
    "        mid = length // 2\n",
    "        is_even = (length % 2) is 0\n",
    "\n",
    "        if is_even:\n",
    "            return (nums[mid - 1] + nums[mid]) / 2\n",
    "\n",
    "        return nums[mid] / 1\n",
    "            \n",
    "    \n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        if not nums2:\n",
    "            return self.findMedianSortedArray(nums1)\n",
    "        \n",
    "        if not nums1:\n",
    "            return self.findMedianSortedArray(nums2)\n",
    "        \n",
    "        left1 = nums1[0]\n",
    "        left2 = nums2[0]\n",
    "        right1 = nums1[-1]\n",
    "        right2 = nums2[-1]\n",
    "        \n",
    "        if left1 < left2:\n",
    "            del nums1[0]\n",
    "            left = left1\n",
    "        else:\n",
    "            del nums2[0]\n",
    "            left = left2\n",
    "            \n",
    "        if right1 >= right2:\n",
    "            nums1.pop()\n",
    "            right = right1\n",
    "        else:\n",
    "            nums2.pop()\n",
    "            right = right2\n",
    "            \n",
    "        if not nums1 and not nums2:\n",
    "            return (left + right) / 2\n",
    "\n",
    "        return self.findMedianSortedArrays(nums1, nums2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import json\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        total_len = len(nums1) + len(nums2)\n",
    "        if total_len & 1 == 0:\n",
    "            return (self.find_kth_number(nums1, nums2, 0, len(nums1), 0, len(nums2), int(total_len / 2)) +\n",
    "                    self.find_kth_number(nums1, nums2, 0, len(nums1), 0, len(nums2), int(total_len / 2 + 1))) / 2\n",
    "        else:\n",
    "            return self.find_kth_number(nums1, nums2, 0, len(nums1), 0, len(nums2), int(total_len / 2 + 1))\n",
    "\n",
    "    def find_kth_number(self, nums1, nums2, start1, len1, start2, len2, k):\n",
    "        \"\"\"\n",
    "        :param nums1:\n",
    "        :param nums2:\n",
    "        :param start1:\n",
    "        :param len1:\n",
    "        :param start2:\n",
    "        :param len2:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if len1 > len2:\n",
    "            return self.find_kth_number(nums2, nums1, start2, len2, start1, len1, k)\n",
    "        if len1 == 0:\n",
    "            return nums2[int(start2 + k - 1)]\n",
    "        if k == 1:\n",
    "            return min(nums1[start1], nums2[start2])\n",
    "        p = min(max(int(k/2), 1), len1)\n",
    "        q = k - p\n",
    "        if nums1[start1 + p - 1] > nums2[start2 + q - 1]:\n",
    "            return self.find_kth_number(nums1, nums2, start1, len1, start2 + q, len2 - q, k - q)\n",
    "        elif nums1[start1 + p - 1] < nums2[start2 + q - 1]:\n",
    "            return self.find_kth_number(nums1, nums2, start1 + p, len1 - p, start2, len2, k - p)\n",
    "        else:\n",
    "            return nums1[start1 + p - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        if nums1 != [] and nums2 != []:\n",
    "            nums = eval(str(nums1)[0:-1] + ',' +  str(nums2)[1:])\n",
    "            nums = sorted(nums)\n",
    "        else :\n",
    "            if nums1 == []:\n",
    "                nums = nums2\n",
    "            else :\n",
    "                nums = nums1\n",
    "        if len(nums)%2 != 0:\n",
    "            return nums[int(len(nums)/2-0.5)]\n",
    "        else :\n",
    "            return (nums[int(len(nums)/2-1)] + nums[int(len(nums)/2)])/2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        nums = nums1 + nums2\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n%2 != 0:\n",
    "            return float(nums[n//2])\n",
    "        return (nums[n//2]+nums[n//2-1])/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        n = nums1 + nums2\n",
    "        n.sort()\n",
    "        l = len(n)\n",
    "        idx = int(l / 2)\n",
    "\n",
    "        #jishu\n",
    "        if l % 2 > 0:\n",
    "            val = n[idx]\n",
    "        else:\n",
    "            #oushu\n",
    "            val = (n[idx] + n[idx-1]) / 2\n",
    "        return val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        if nums1 or nums2:\n",
    "            nums_temp = nums1+nums2\n",
    "            nums3 = sorted(nums_temp)\n",
    "            nu = (len(nums3))%(2.0)\n",
    "            n = int((len(nums3))//(2.0))\n",
    "            if nu!=0.0:\n",
    "                return nums3[n]\n",
    "            else:\n",
    "                need = (nums3[n-1]+nums3[n])/2.0\n",
    "                return need\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, A: List[int],B: List[int]) -> float:\n",
    "        m, n = len(A), len(B)\n",
    "        # 让集合A是比较短的那个？ 个数为m\n",
    "        # 让搜索更短一些？\n",
    "        if m > n:\n",
    "            A, B, m, n = B, A, n, m\n",
    "        # 如果大的n长度也为0的话，说明两个集合都是空集\n",
    "        if n == 0:\n",
    "            raise ValueError\n",
    "\n",
    "        # 条件1\n",
    "        imin, imax, half_len = 0, m, (m + n + 1) // 2\n",
    "        \n",
    "        while imin <= imax:\n",
    "            i = (imin + imax) // 2\n",
    "            j = half_len - i\n",
    "            \n",
    "            # 二分法查找\n",
    "            if i < m and B[j-1] > A[i]:\n",
    "                # B的最大值大了，即 j 大了，需要让i增大，因此二分法的下界变成i+1\n",
    "                imin = i + 1\n",
    "            elif i > 0 and A[i-1] > B[j]:\n",
    "                # A的最大值大了，即 i 大了，需要让i减小，因此二分法的上界变成i-1\n",
    "                imax = i - 1\n",
    "            else:\n",
    "                # 已将AB对半分开了\n",
    "\n",
    "                # left判断\n",
    "                if i == 0: max_of_left = B[j-1]\n",
    "                elif j == 0: max_of_left = A[i-1]\n",
    "                else: max_of_left = max(A[i-1], B[j-1])  # 如果不做前面的==0判断，这里index会-1\n",
    "\n",
    "                # 如果总个数为奇数，中位数就是左边的最大值（为啥不是右边最小值....一定是左边个数多咩？）\n",
    "                if (m + n) % 2 == 1:\n",
    "                    return max_of_left\n",
    "\n",
    "                # 如果总个数是偶数，需要再计算右边的最小值，然后再求平均\n",
    "                if i == m: min_of_right = B[j]\n",
    "                elif j == n: min_of_right = A[i]\n",
    "                else: min_of_right = min(A[i], B[j])\n",
    "\n",
    "                return (max_of_left + min_of_right) / 2.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        if len(nums1) > len(nums2):\n",
    "            tmp = nums1\n",
    "            nums1 = nums2\n",
    "            nums2 = tmp\n",
    "        \n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        left = 0\n",
    "        right = m \n",
    "        total_left = (m + n + 1) // 2\n",
    "        while(left < right):\n",
    "            i = left + (right - left + 1)//2\n",
    "            j = total_left - i \n",
    "            # print(i,\" \",j)\n",
    "            if nums1[i-1] > nums2[j]:\n",
    "                right = i -1\n",
    "            else:\n",
    "                left = i\n",
    "        i = left\n",
    "        j = total_left - i \n",
    "        import sys\n",
    "        max_value = sys.maxsize\n",
    "        min_value = -sys.maxsize - 1\n",
    "        leftmax1 =  min_value if i == 0 else nums1[i-1]\n",
    "        leftmax2 = min_value if j == 0  else nums2[j-1]\n",
    "        rightmin1 = max_value if i == m  else nums1[i]\n",
    "        rightmin2 = max_value if j == n  else nums2[j]\n",
    "        if ((m+n)%2 == 1):\n",
    "            return max(leftmax1, leftmax2)\n",
    "        else:\n",
    "            return (max(leftmax1, leftmax2) + min(rightmin1, rightmin2)) / 2\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMedian(self,nums):\n",
    "        length = len(nums)\n",
    "        if length%2:\n",
    "            return nums[length//2]\n",
    "        else:\n",
    "            return (nums[length//2]+nums[length//2-1])/2\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        if len(nums1)==0:\n",
    "            return self.getMedian(nums2)\n",
    "        if len(nums2)==0:\n",
    "            return self.getMedian(nums1)\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        len1 = len(nums1)\n",
    "        len2 = len(nums2)\n",
    "        merge = []\n",
    "        while(True):\n",
    "            if nums1[p1]<=nums2[p2]:\n",
    "                merge.append(nums1[p1])\n",
    "                p1 += 1\n",
    "            else:\n",
    "                merge.append(nums2[p2])\n",
    "                p2 += 1\n",
    "            if p1==len1:\n",
    "                merge += nums2[p2:]\n",
    "                break\n",
    "            elif p2==len2:\n",
    "                merge += nums1[p1:]\n",
    "                break\n",
    "        return self.getMedian(merge)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        (nums1, nums2) = (nums1, nums2) if len(\n",
    "            nums1) <= len(nums2) else (nums2, nums1)\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        total_left = (m+n+1)//2\n",
    "        left = 0\n",
    "        right = m\n",
    "        while left < right:\n",
    "            i = left+(right-left)//2\n",
    "            j = total_left-i\n",
    "            if nums2[j-1] > nums1[i]:\n",
    "                left = i+1\n",
    "            else:\n",
    "                right = i\n",
    "        i = left\n",
    "        j = total_left-i\n",
    "        nums1LeftMax = float(\"-inf\") if i == 0 else nums1[i-1]\n",
    "        nums1RightMIn = float(\"inf\") if i == m else nums1[i]\n",
    "        nums2LeftMax = float(\"-inf\") if j == 0 else nums2[j-1]\n",
    "        nums2RightMIn = float(\"inf\") if j == n else nums2[j]\n",
    "\n",
    "        if (m+n) % 2 == 1:\n",
    "            return max(nums1LeftMax, nums2LeftMax)\n",
    "        else:\n",
    "            return (max(nums1LeftMax, nums2LeftMax)+min(nums1RightMIn, nums2RightMIn))/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        def Median(l):\n",
    "            N=len(l)\n",
    "            if N%2==0:\n",
    "                return (l[N//2]+l[N//2-1])/2\n",
    "            else:\n",
    "                return l[N//2]\n",
    "        m=len(nums1)\n",
    "        n=len(nums2)\n",
    "        if m==0 and n==0:\n",
    "            return float(0)\n",
    "        elif n==0:\n",
    "            return Median(nums1)\n",
    "        elif m==0:\n",
    "            return Median(nums2)\n",
    "        else:\n",
    "            for num in nums2:\n",
    "                nums1.append(num)\n",
    "            nums1=sorted(nums1)\n",
    "            return Median(nums1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        k1 = (len(nums1) + len(nums2) + 1) // 2 \n",
    "        k2 = (len(nums1) + len(nums2) + 2) // 2 \n",
    "        def cal_k(nums1, nums2, k):\n",
    "            if len(nums2) > len(nums1):\n",
    "                nums1, nums2 = nums2, nums1\n",
    "            if len(nums2) == 0:\n",
    "                return nums1[k - 1]\n",
    "            if k == 1:\n",
    "                return min(nums1[0], nums2[0])\n",
    "            else:\n",
    "                t = min(len(nums2), k // 2)\n",
    "                if nums1[t - 1] >= nums2[t - 1]:\n",
    "                    return cal_k(nums1, nums2[t:], k - t)\n",
    "                else:\n",
    "                    return cal_k(nums1[t:], nums2, k - t)\n",
    "        return (cal_k(nums1, nums2, k1) + cal_k(nums1, nums2, k2)) / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        nums1.extend(nums2)\n",
    "\n",
    "        def divide(nums: List[int], left: int, right: int):\n",
    "            if left >= right:\n",
    "                return\n",
    "            mid = ((right + left) >> 1)\n",
    "            divide(nums, left, mid)\n",
    "            divide(nums, mid + 1, right)\n",
    "            merge(nums, left, mid, right)\n",
    "\n",
    "        def merge(nums: List[int], left: int, mid: int, right: int):\n",
    "            lindex, rindex = left, mid + 1\n",
    "            t = []\n",
    "            while lindex <= mid and rindex <= right:\n",
    "                print(lindex, rindex)\n",
    "                if nums[lindex] > nums[rindex]:\n",
    "                    t.append(nums[rindex])\n",
    "                    rindex += 1\n",
    "                else:\n",
    "                    t.append(nums[lindex])\n",
    "                    lindex += 1\n",
    "            while lindex <= mid:\n",
    "                t.append(nums[lindex])\n",
    "                lindex += 1\n",
    "\n",
    "            while rindex <= right:\n",
    "                t.append(nums[rindex])\n",
    "                rindex += 1\n",
    "\n",
    "            for i in range(len(t)):\n",
    "                nums[left + i] = t[i]\n",
    "        divide(nums1, 0, len(nums1) - 1)\n",
    "\n",
    "        mid = len(nums1)//2\n",
    "\n",
    "        return nums1[mid] if len(nums1)%2 else (nums1[mid] + nums1[mid - 1])/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        \n",
    "        def binary_search(i, j, k):\n",
    "            h1 = min(k//2, m-i)\n",
    "            h2 = min(k//2, n-j)\n",
    "            # print(i, j, k)\n",
    "            # if k == 1:\n",
    "            #     ipdb.set_trace()\n",
    "            if i >= m:\n",
    "                # print('i>=m exit')\n",
    "                return nums2[j+k-1]\n",
    "            elif j >= n:\n",
    "                # print('j>=n exit')\n",
    "                return nums1[i+k-1]\n",
    "            elif k == 1:\n",
    "                # print('k==1 exit')\n",
    "                return min(nums1[i], nums2[j])\n",
    "            else:\n",
    "                if nums1[i+h1-1] < nums2[j+h2-1]:\n",
    "                    return binary_search(i+h1, j, k-h1)\n",
    "                else:\n",
    "                    return binary_search(i, j+h2, k-h2)\n",
    "    \n",
    "        return (binary_search(0, 0, (m+n+1)//2)+binary_search(0, 0, (m+n+2)//2))/2.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        new_l = merge(nums1,nums2)\n",
    "        n = len(new_l)\n",
    "        if n%2 == 0:\n",
    "            m = (n-1) // 2\n",
    "            ans = (new_l[m]+new_l[m+1])/2\n",
    "        else:\n",
    "             m = (n-1) // 2\n",
    "             ans = float(new_l[m])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def merge(nums1,nums2):\n",
    "    ###合并两个有序数组\n",
    "    if not nums2:\n",
    "        return nums1\n",
    "    if not nums1:\n",
    "        return nums2\n",
    "    m = len(nums1)\n",
    "    n = len(nums2)\n",
    "    res = []\n",
    "    i = j = 0\n",
    "    while i < m and j < n:\n",
    "        if nums1[i] < nums2[j]:\n",
    "            res.append(nums1[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            res.append(nums2[j])\n",
    "            j += 1\n",
    "    res.extend(nums1[i:])\n",
    "    res.extend(nums2[j:])\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        nums = nums1 + nums2\n",
    "        nums.sort()\n",
    "        mid = len(nums) // 2\n",
    "        res = round((nums[mid] + nums[~mid]) / 2, 5)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        median=0\n",
    "\n",
    "\n",
    "        nums_all=sorted(nums1+nums2)\n",
    "        if len(nums_all)%2==1:\n",
    "            median=nums_all[len(nums_all)//2]\n",
    "        else:\n",
    "            median=(nums_all[len(nums_all)//2-1]+nums_all[len(nums_all)//2])/2\n",
    "\n",
    "        return median"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        median=0\n",
    "\n",
    "\n",
    "        nums_all=sorted(nums1+nums2)\n",
    "        if len(nums_all)%2==1:\n",
    "            median=nums_all[len(nums_all)//2]\n",
    "        else:\n",
    "            median=(nums_all[len(nums_all)//2-1]+nums_all[len(nums_all)//2])/2\n",
    "\n",
    "        return median"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        if not nums1 or not nums2:\n",
    "            nums = nums1 if nums1 else nums2\n",
    "            if len(nums) % 2 == 0:\n",
    "                index = len(nums) >> 1\n",
    "                return (nums[index] + nums[index-1]) / 2\n",
    "            return nums[len(nums) >> 1]\n",
    "\n",
    "        curMaxValue = None\n",
    "        i1 = i2 = 0\n",
    "        for i in range( (len(nums1) + len(nums2) + 1) >> 1 ):\n",
    "            # 较小者往前移动，并记录当前第i+1大的值\n",
    "            if i1 < len(nums1) and i2 < len(nums2):\n",
    "                if nums1[i1] <= nums2[i2]:\n",
    "                    curMaxValue = nums1[i1]\n",
    "                    i1 += 1\n",
    "                else:\n",
    "                    curMaxValue = nums2[i2]\n",
    "                    i2 += 1\n",
    "            elif i1 == len(nums1):\n",
    "                curMaxValue = nums2[i2]\n",
    "                i2 += 1\n",
    "            else:\n",
    "                curMaxValue = nums1[i1]\n",
    "                i1 += 1\n",
    "\n",
    "        if (len(nums1) + len(nums2)) % 2 == 1:\n",
    "            return curMaxValue\n",
    "\n",
    "        if i1 == len(nums1):\n",
    "            nextValue = nums2[i2]\n",
    "        elif i2 == len(nums2):\n",
    "            nextValue = nums1[i1]\n",
    "        else:\n",
    "            nextValue = min(nums1[i1], nums2[i2])\n",
    "\n",
    "        return (curMaxValue + nextValue) / 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        left = int((m+n+1)/2)\n",
    "        right = int((m+n+2)/2)\n",
    "        def getKth(nums1, start1, end1, nums2, start2, end2, k):\n",
    "            print(start1, end1, start2, end2, k)\n",
    "            if end1-start1 > end2-start2:\n",
    "                return getKth(nums2, start2, end2, nums1, start1, end1, k)\n",
    "            \n",
    "            if end1-start1+1==0:\n",
    "                return nums2[start2+k-1]\n",
    "            if k==1:\n",
    "                return min(nums1[start1], nums2[start2])\n",
    "            \n",
    "            new_start1 = int(start1 + min(end1-start1+1, k/2)-1)\n",
    "            new_start2 = int(start2 + min(end2-start2+1, k/2)-1)\n",
    "            if nums1[new_start1]>nums2[new_start2]:\n",
    "                return getKth(nums1, start1, end1, nums2, new_start2+1, end2, k-(new_start2-start2+1))\n",
    "            else:\n",
    "                return getKth(nums1, new_start1+1, end1, nums2, start2, end2, k-(new_start1-start1+1))\n",
    "        print(getKth(nums1, 0, m-1, nums2, 0, n-1, left))\n",
    "        print(getKth(nums1, 0, m-1, nums2, 0, n-1, right))\n",
    "        return (getKth(nums1, 0, m-1, nums2, 0, n-1, left) + getKth(nums1, 0, m-1, nums2, 0, n-1, right)) / 2\n",
    "\n",
    "              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        ans=nums1+nums2\n",
    "        ans=sorted(ans)\n",
    "        if len(ans)%2==0:\n",
    "           a=len(ans)//2\n",
    "           return (ans[a]+ans[a-1])/2\n",
    "        else:\n",
    "           b=len(ans)//2\n",
    "           return ans[b]\n",
    "            \n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "\n",
    "        def findnum(target, nums1, nums2):\n",
    "            count = 0\n",
    "            p1, p2 = 0, 0\n",
    "\n",
    "            while count <= target:\n",
    "                if count == target:\n",
    "                    if p1 >= len(nums1):\n",
    "                        return(nums2[p2])\n",
    "                    elif p2 >= len(nums2):\n",
    "                        return(nums1[p1])\n",
    "                    else:\n",
    "                        if nums1[p1] <= nums2[p2]:\n",
    "                            return(nums1[p1])\n",
    "                        else:\n",
    "                            return(nums2[p2])\n",
    "                else:\n",
    "                    if p1 >= len(nums1):\n",
    "                        p2 = p2+1\n",
    "                    elif p2 >= len(nums2):\n",
    "                        p1 = p1+1\n",
    "                    else:\n",
    "                        if nums1[p1] <= nums2[p2]:\n",
    "                            p1 = p1+1\n",
    "                        else:\n",
    "                            p2 = p2+1\n",
    "                    count = count + 1\n",
    "\n",
    "        if (len(nums1) + len(nums2)) % 2 == 0:\n",
    "            target1 = (len(nums1) + len(nums2))/2-1\n",
    "            target2 = (len(nums1) + len(nums2))/2\n",
    "            return((findnum(target1, nums1, nums2)+findnum(target2, nums1, nums2))/2)\n",
    "        else:\n",
    "            target1 = (len(nums1) + len(nums2)-1)/2\n",
    "            return(findnum(target1, nums1, nums2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        nums3, n = sorted(nums1 + nums2), len(nums1) + len(nums2)\n",
    "        return nums3[n // 2] if n % 2 == 1 else (nums3[n // 2] + nums3[n // 2 - 1]) / 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:\n",
    "        nums3, n = sorted(nums1 + nums2), len(nums1) + len(nums2)\n",
    "        return nums3[n // 2] if n % 2 == 1 else (nums3[n // 2] + nums3[n // 2 - 1]) / 2 "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
